//题中给出一个 n_rows 行 n_cols 列的二维矩阵，且所有值被初始化为 0。要求编写一个 flip 函数，均匀随机的将矩阵中的 0 变为 1，并返回
//该值的位置下标 [row_id,col_id]；同样编写一个 reset 函数，将所有的值都重新置为 0。尽量最少调用随机函数 Math.random()，并且
//优化时间和空间复杂度。 
//
// 注意: 
//
// 
// 1 <= n_rows, n_cols <= 10000 
// 0 <= row.id < n_rows 并且 0 <= col.id < n_cols 
// 当矩阵中没有值为 0 时，不可以调用 flip 函数 
// 调用 flip 和 reset 函数的次数加起来不会超过 1000 次 
// 
//
// 示例 1： 
//
// 输入: 
//["Solution","flip","flip","flip","flip"]
//[[2,3],[],[],[],[]]
//输出: [null,[0,1],[1,2],[1,0],[1,1]]
// 
//
// 示例 2： 
//
// 输入: 
//["Solution","flip","flip","reset","flip"]
//[[1,2],[],[],[],[]]
//输出: [null,[0,0],[0,1],null,[0,0]] 
//
// 输入语法解释： 
//
// 输入包含两个列表：被调用的子程序和他们的参数。Solution 的构造函数有两个参数，分别为 n_rows 和 n_cols。flip 和 reset 没
//有参数，参数总会以列表形式给出，哪怕该列表为空 
// Related Topics 水塘抽样 哈希表 数学 随机化 
// 👍 37 👎 0

  
package com.zwy.leetCode.editor.cn;

import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class RandomFlipMatrix{
    public static void main(String[] args) {
        Solution solution = new RandomFlipMatrix().new Solution(3,1);
        solution.flip();
        solution.flip();
        solution.flip();
        solution.reset();
        solution.flip();
      }
      //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
          Random r = new Random();
          Map<Integer,Integer> map = new HashMap<>();
          int n;
          int m;
          int i;
          public Solution(int n_rows, int n_cols) {
              n=n_rows;
              m=n_cols;
          }

          public int[] flip() {
              change(i,r.nextInt(n*m-i)+i);
              int t = get(i++);
              return new int[]{t%n,t/n};
          }
          public int get(int j){
              return map.getOrDefault(j,j);
          }
          public void change(int j,int k){
              int a = get(j);
              int b = get(k);
              map.put(j,b);
              map.put(k,a);
          }

          public void reset() {
              map.clear();
              i=0;
          }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(m, n);
 * int[] param_1 = obj.flip();
 * obj.reset();
 */
//leetcode submit region end(Prohibit modification and deletion)

}